#Aaron McCarty and Conrad Dean

#    This file is part of EAP.
#
#    EAP is free software: you can redistribute it and/or modify
#    it under the terms of the GNU Lesser General Public License as
#    published by the Free Software Foundation, either version 3 of
#    the License, or (at your option) any later version.
#
#    EAP is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
#    GNU Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with EAP. If not, see <http://www.gnu.org/licenses/>.

import random
import operator
import copy

from eap import base
from eap import creator
from eap import toolbox
import matplotlib.pyplot as pyplot

creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
creator.create("Population", list)

tools = toolbox.Toolbox()
# Attribute generator
tools.register("attr_bool", random.randint, 0, 1)
# Structure initializers
tools.register("individual", creator.Individual,
    content_init=tools.attr_bool, size_init=100)
tools.register("population", creator.Population,
    content_init=tools.individual, size_init=100)

#Fitness Landscapes
def evalOneMax(individual):
    return sum(individual),

def doubleMaximaUneven(individual):
    return abs(sum(individual) - 40),
    

def twoPeaksDiffWidthSameHeight(individual):
    x = sum(individual)
    y = (x-60)*1.5 if x>60 else (60-x)
    return 1.3**y,
    

def twoPeakEqualWidthDiffHeight(individual):
    x = sum(individual)
    y = (x-50)*1.1 if x>50 else (50-x)
    return 1.3**y,
    

def doubleMaximaRightHeavy(individual):
    """f(50) is zero, f(0) is 25, f(100) is 100"""
    x = sum(individual)
    landscape = abs(x - 50)
    if x < 50:
        return landscape,
    else:
        return landscape*3,

def middlePeak(individual):
    """50 is the peak, tapers off to 0 at the ends"""
    return abs(abs((sum(individual)-50))-50),

def sherriFitnessLandscape(individual):
    """Makes two peaks at 0 and 100.  global min at 50"""
    return 1.3**(abs(sum(individual)-50)),

# Operator registering
tools.register("evaluate", doubleMaximaUneven)
tools.register("mate", toolbox.cxTwoPoints)
tools.register("mutate", toolbox.mutFlipBit, indpb=.1)



def genericGeneration(pop):
    """ A boring generation type """
    tools.register("select", toolbox.selRoulette)
    CXPB, MUTPB, NGEN = 0.5, 0.2, 100
    offsprings = tools.select(pop, n=len(pop))
    offsprings = map(tools.clone, offsprings)
    # Apply crossover and mutation on the offsprings
    for child1, child2 in zip(offsprings[::2], offsprings[1::2]):
        if random.random() < CXPB:
            tools.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values

    for mutant in offsprings:
        if random.random() < MUTPB:
            tools.mutate(mutant)
            del mutant.fitness.values

    # Evaluate the individuals with an invalid fitness
    invalid_ind = [ind for ind in offsprings if not ind.fitness.valid]
    fitnesses = map(tools.evaluate, invalid_ind)
    for ind, fit in zip(invalid_ind, fitnesses):
        ind.fitness.values = fit
    
    # The population is entirely replaced by the offsprings
    pop[:] = offsprings

def fitnessSharingGeneration(pop):
    tools.register("select", toolbox.selRoulette)
    #tools.register("select", toolbox.selBest)
    CXPB, MUTPB, NGEN = 0.5, 0.8, 100
    threshold = 25
    offsprings = []
    for i in range(len(pop)/2):
        children = chooseCloseParents(pop, threshold)
        offsprings += children
        
    
    offsprings = map(tools.clone, offsprings)
    # Apply crossover and mutation on the offsprings
    for child1, child2 in zip(offsprings[::2], offsprings[1::2]):
        if random.random() < CXPB:
            tools.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values

    valid_ind = [ind for ind in offsprings if ind.fitness.valid]
    for mutant in valid_ind:
        if random.random() < MUTPB:
            #,indpb=abs(random.gauss(0,.5))
            tools.mutate(mutant)
            del mutant.fitness.values

    # Evaluate the individuals with an invalid fitness
    invalid_ind = [ind for ind in offsprings if not ind.fitness.valid]
    fitnesses = map(tools.evaluate, invalid_ind)
    for ind, fit in zip(invalid_ind, fitnesses):
        ind.fitness.values = fit
    
    #Apply nichecount thing
    fitnessesShared(offsprings)
    pop[:] = tools.select(offsprings, n=len(offsprings))
        

def fitnessesShared(population):
    """
    Updates the given population's fitnesses with the per-individual calculated niche count
    """
    nicheCounts = [nicheCount(ind, population) for ind in population]
    for ind, NC in zip(population, nicheCounts):
        ind.fitness.values = ind.fitness.values[0]/NC,

def nicheCount(individual, population):
    """
    Calculates the niche count for the given individual in the given population
    """
    count = 0
    radius = 25
    someAlpha = 2
    for ind in population:
        r = radius
        d = hammingDistance(individual, ind)
        if d > r:
            proportionYouAddToNicheCount = 0
        else:
            proportionYouAddToNicheCount = 1 - (d/r)**someAlpha
            
        count += proportionYouAddToNicheCount
    return count #will return 1, since at least the individual is within its niche radius
    

def hammingDistance(ind1, ind2):
    """
    Calculates the hamming distance between two individuals.
    You must give it two individuals of type list that are of equal length.
    """
    assert len(ind1) == len(ind2), "lengths of individuals unequal:%s != %s" % (len(ind1), len(ind2))
    count = 0
    '''count the number of bit flips needed to move from one genome to the other'''
    for i in range(len(ind1)):
        if ind1[i] != ind2[i]:
            count += 1
    return count

def distance(ind1, ind2):
    """
    Calculate the distance between two individuals.
    Doesn't use Hamming Distance, but instead bases it off
    of the distance between the individuals in the search space.
    """
    d1 = sum(ind1)
    d2 = sum(ind2)
    return abs(d2-d1)


def chooseCloseParents(population, threshold):
    """
    With a given population, selects two random parents
    from the given population and returns them to the caller.
    """
    random.shuffle(population)
    firstParent = population.pop(0)
    for possibleParent in population:
        if hammingDistance(firstParent, possibleParent) < threshold:
            population.remove(possibleParent)
            return [firstParent,possibleParent]
    population.remove(possibleParent)
    return [firstParent,possibleParent]

    

def crowdingGeneration(pop):
    """
    Generation method that implements crowding.
    """
    MUTPB = .5
    parentsChosen = False
    threshold = 25
    """
    Select candidate parents
    """
    while not parentsChosen:
        parentsChosen = chooseCloseParents(pop,threshold)
    children = map(tools.clone, parentsChosen)
    """
    Perform the crossover
    """
    tools.mate(children[0],children[1])
    toAdd = [parentsChosen[0],parentsChosen[1]]
    for ch in children:
        """
        Mutate the child
        """
        if random.random() < MUTPB:
            #,indpb=abs(random.gauss(0,.5))
            tools.mutate(ch)
        """
        Fitness calculation
        """
        ch.fitness.values = tools.evaluate(ch)
        """
        Match child with closer parent, then see which of the two is better
        """
        if distance(ch, parentsChosen[0]) > distance(ch,parentsChosen[1]):
            if ch.fitness.values > toAdd[1].fitness.values:
                toAdd[1] = ch
        else:
            if ch.fitness.values > toAdd[0].fitness.values:
                toAdd[0] = ch
    for ind in toAdd:
        if ind != None:
            pop.append(ind)
             
    

def runTest(generations,fitnessLandscape,selectionType,generationType):
    """Runs a test with the given parameters"""
    random.seed(3)
    
    tools.register("evaluate", fitnessLandscape)
    tools.register("doGeneration", generationType)
    
    """Initialize the population"""
    pop = tools.population()

    """Set the title name for the tests, labeling the graphs"""
    fitnessLandscapeName = "Landscape: "+str(tools.evaluate.__name__).split(" ")[1]
    generationTypeName = "Generation Type: "+str(tools.doGeneration.__name__).split(" ")[1]
    populationSize = "# Individuals: "+ str(len(pop))
    generationNumber = "# Generations: "+ str(generations)
    testTitle = fitnessLandscapeName+" "+populationSize+"\n"+generationTypeName+" "+generationNumber

    """ These forloops give an even distribution in the search space """
    #"""
    for i in range(len(pop)):
        for j in range(i):
            pop[i][j] = 0
        for j in range(i,100):
            pop[i][j] = 1
        random.shuffle(pop[i])
    
    #"""
    
    """ generates an even distribution population for the purpose of
    drawing a line on the graphs"""
    singlepoint = [0 for i in range(100)]
    landscape = [singlepoint[:] for i in range(100)]
    for i in range(len(landscape)):
        for j in range(i):
            landscape[i][j] = 1
        for j in range(i,100):
            landscape[i][j] = 0
            
    CXPB, MUTPB, NGEN = 0.5, 0.2, generations
    
    print "Start of evolution"
    print testTitle
    
    # Evaluate the entire population
    fitnesses = map(tools.evaluate, pop)
    for ind, fit in zip(pop, fitnesses):
        ind.fitness.values = fit
    
    print "  Evaluated %i individuals" % len(pop)
    globalEvaluations = 0

    #pyplot.ion()
    landscape = map(tools.evaluate, landscape)
    landscape = [item[0] for item in landscape]
    display = pyplot.figure()



    interval = generations/5
    display.add_subplot(NGEN/interval+1,1,0/interval+1)
    pyplot.scatter(range(100),landscape, s=1)

    # Begin the evolution
    for g in range(NGEN+1):
        #print "-- Generation %i --" % g
        tools.doGeneration(pop)

        """
        genotypeFits is the list of individuals based on their location
        in the search space so we can populate our histogram graph
        """
        genotypeFits = [sum(ind) for ind in pop]
        
        if g % interval == 0:
            """At regular intervals, display progress so far."""
            counts = [0 for i in range(101)] #Initialize the population histogram
            for f in genotypeFits:
                counts[int(f)] += 1  #Keep track of fitness frequencies
            display.add_subplot(NGEN/interval+1,1,g/interval+1)
            pyplot.bar(range(101),counts)
            pyplot.suptitle(testTitle)
            pyplot.xlim(0,101)
            pyplot.ylim(0,50)
            #pyplot.draw()
    pyplot.savefig(fitnessLandscapeName+generationTypeName+"gen"+generationNumber+"pop"+populationSize+".png",format='png')
    print "-- End of (successful) evolution --"

def tests():
    """
    *Available Fitness Landscapes*
    evalOneMax
    doubleMaximaUneven
    twoPeaksDiffWidthSameHeight
    twoPeakEqualWidthDiffHeight
    doubleMaximaRightHeavy
    middlePeak
    sherriFitnessLandscape
    """
    #runTest(100,evalOneMax,None,crowdingGeneration)
    #runTest(5000,sherriFitnessLandscape,None,crowdingGeneration)
    
    
    runTest(300,doubleMaximaUneven,None,fitnessSharingGeneration)
    runTest(300,doubleMaximaRightHeavy,None,fitnessSharingGeneration)
    runTest(300,sherriFitnessLandscape,None,fitnessSharingGeneration)
    runTest(300,twoPeaksDiffWidthSameHeight,None,fitnessSharingGeneration)
    runTest(7000,twoPeakEqualWidthDiffHeight,None,fitnessSharingGeneration)


    runTest(7000,doubleMaximaUneven,None,crowdingGeneration)
    runTest(7000,doubleMaximaRightHeavy,None,crowdingGeneration)
    runTest(7000,sherriFitnessLandscape,None,crowdingGeneration)
    runTest(7000,twoPeaksDiffWidthSameHeight,None,crowdingGeneration)
    runTest(7000,twoPeaksDiffWidthSameHeight,None,crowdingGeneration)
    runTest(7000,twoPeakEqualWidthDiffHeight,None,crowdingGeneration)
    
    
    

    """
    #runTest(40,middlePeak,None,fitnessSharingGeneration)
    runTest(80,doubleEvenMaximaUneven,None,fitnessSharingGeneration)
    runTest(40,doubleMaximaRightHeavy,None,fitnessSharingGeneration)
    #"""
    """
    runTest(6000,doubleEvenMaximaUneven,None,crowdingGeneration)
    runTest(6000,doubleMaximaUneven,None,crowdingGeneration)
    runTest(6000,doubleMaximaRightHeavy,None,crowdingGeneration)
    """
    
if __name__ == "__main__":
    tests()
    
    raw_input("close")
